package Top_Interview_Questions.String;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/15 11:41
 * <p>
 * https://leetcode-cn.com/problems/basic-calculator-ii/solution/zhan-de-jing-dian-ying-yong-ji-suan-qi-by-nopdes1r/
 *
 * https://leetcode-cn.com/problems/basic-calculator-ii/solution/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/
 * labuladong的可能效率更高，但是没有java代码
 */
public class _0227 {


    public int calculate(String exp) {
        return calRst(backTempExp(exp));
    }

    // 计算最终的结果
    public static int calRst(LinkedList<String> tempBackExp) {
        Stack<Integer> calStk = new Stack<Integer>();
        for (String c : tempBackExp) {
            // 1.数字，入栈
            if (isNumeric(c)) {
                calStk.push(Integer.valueOf(c)); // string to int
                continue;
            }
            // 2.非数字，则为符号，出栈两个元素计算出结果然后再入栈该计算值
            else {
                int a = calStk.pop();
                int b = calStk.pop();
                switch (c.toCharArray()[0]) {
                    // 注意减法和除法时，注意出栈的顺序与原表达式是相反的

                    case '+':
                        calStk.push(b + a);
                        continue;
                    case '-':
                        calStk.push(b - a);
                        continue;
                    case '*':
                        calStk.push(b * a);
                        continue;
                    case '/':
                        calStk.push(b / a);
                        continue;
                }
            }
        }
        return calStk.pop();
    }


    // 计算后缀表达式
    public static LinkedList<String> backTempExp(String exp) {

        Stack<String> stkEles = new Stack<String>();
        LinkedList<String> tempBackExp = new LinkedList<String>();
        for (int i = 0; i < exp.length(); i++) {
            // 1.遇到了数字
            if (Character.isDigit(exp.charAt(i))) {
                // 注意多位数的获取
                int k = i + 1;
                for (; k < exp.length() && Character.isDigit(exp.charAt(k)); k++) {

                }
                tempBackExp.add(exp.substring(i, k));
                i = k - 1;// 更新 i
                continue;
            }
            // 2.遇到了乘除运算符
            if (exp.charAt(i) == '/' || exp.charAt(i) == '*') {

                while (!stkEles.isEmpty() && (stkEles.lastElement().equals("/") || stkEles.lastElement().equals("*"))) {
                    tempBackExp.add(stkEles.pop()); // 弹出优先级相同或以上的栈内运算符
                }
                stkEles.add(String.valueOf(exp.charAt(i))); // 运算符入栈
                continue;
            }
            // 3.遇到了加减运算符
            if (exp.charAt(i) == '+' || exp.charAt(i) == '-') {
                while (!stkEles.isEmpty() && !isNumeric(stkEles.lastElement())) {
                    tempBackExp.add(stkEles.pop()); // 弹出优先级相同或以上的栈内运算符
                }
                stkEles.add(String.valueOf(exp.charAt(i))); // 运算符入栈
                continue;
            }
        }
        // 4.最后弹出栈内所有元素到表达式
        while (stkEles.size() > 0) {
            tempBackExp.add(stkEles.pop());
        }
        return tempBackExp;
    }


    public static boolean isNumeric(String str) {
        for (int i = 0; i < str.length(); i++) {
            if (!Character.isDigit(str.charAt(i))) {
                return false;
            }
        }
        return true;
    }


}
